高考申論題
109年
[資訊處理] 資料結構
第 三 題
📖 題組：
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
二、優先佇列（Priority Queue）是依管理物件的優先權來考量，在此我們考慮管理物件的鍵值（Key）愈小其優先權愈高，兩個主要操作則分別為加入（Insert）與擷取最小者（Delete_Min）。
二元堆積（Binary Heap）是一個優先佇列的資料結構，因為我們考慮鍵值小的物件有高的優先權，所以又可稱為最小堆積（Minimum Heap）。（14分）
⑴在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此陣列對應的完全二元樹（以樹狀結構表示）。
Index 1 2 3 4 5 6 7 8 9 10
Key 35 18 42 24 7 14 25 12 38 21
⑵請說明二元堆積中何謂堆積特性（Heap Property）？
⑶前揭⑴中的完全二元樹並未有堆積特性，請將其進行堆積化（Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。
⑴在結構上最小堆積為一個完全二元樹（Complete Binary Tree），若使用一個陣列來實作最小堆積，陣列中物件的鍵值放置如下，請描述此陣列對應的完全二元樹（以樹狀結構表示）。
Index 1 2 3 4 5 6 7 8 9 10
Key 35 18 42 24 7 14 25 12 38 21
⑵請說明二元堆積中何謂堆積特性（Heap Property）？
⑶前揭⑴中的完全二元樹並未有堆積特性，請將其進行堆積化（Heapify），並以陣列表示出堆積化後的最小堆積所對應之完全二元樹。
📝 此題為申論題
思路引導 VIP
⑴ 將陣列內容由上而下、由左至右畫成二元樹即可。 ⑵ 堆積特性包含兩個重點：形狀特性(完全二元樹) 與 排序特性(父節點與子節點大小關係)。
🤖
AI 詳解
AI 專屬家教
【考點分析】 二元堆積的陣列表示法、最小堆積特性（Min-Heap Property）、建堆（Build-Heap / Heapify）演算法過程。 【理論/法規依據】
▼ 還有更多解析內容